#include <iostream>
#include <math.h>

using namespace std;
class Solution
{
public:
    /**
     * @brief
     * s=n*(n+1)/2
     * @param n
     * @return int
     */
    int arrangeCoins(int n)
    {
        // return (sqrt( 1 + 8 * n) - 1) / 2;
        return sqrt(2 * (long)n + 0.25) - 0.5;
    }

    int arrangeCoins_2(int n)
    {
        long left = 0, right = n;
        long k, curr;
        while (left <= right)
        {
            k = left + (right - left) / 2;
            curr = k * (k + 1) / 2;

            if (curr == n)
            {
                return (int)k;
            }

            if (n < curr)
            {
                right = k - 1;
            }
            else
            {
                left = k + 1;
            }
        }
        return (int)right;
    }
};
int main()
{
    Solution s;
    cout << s.arrangeCoins(5) << endl;
    return 0;
}
